www.gusucode.com > VC 2D游戏编辑器-源码程序 > VC 2D游戏编辑器-源码程序/code/game_Source/GameLib/findpathA.cpp

    //Download by http://www.NewXing.com
#include "globle.h"
#include "globle_func.h"
#include "..\\newgame.h"
#include "findpathA.h"

#define MAXINT 32767


FINDPATH_A8::FINDPATH_A8( )
{
	sort_queue	= NULL;
	store_queue	= NULL;
	pLink		= NULL;
	dis_map		= NULL;
	path1_X		= NULL;
	path1_Y		= NULL;
	bBeginDir	= false;
	IsFound		= false;
	memset(pathX, -1, TABLE_X*TABLE_Y*sizeof(int));
	memset(pathY, -1, TABLE_X*TABLE_Y*sizeof(int));
}

void FINDPATH_A8::find(long StartX, long StartY, long EndX, long EndY)
{
	IsFound	= false;
	level = 0;
	if(sort_queue)
	{
		while(sort_queue)
		{
			pLink = sort_queue;
			sort_queue = sort_queue->Next;
			P_SAFE_DELETE(pLink);
		}
		sort_queue= NULL;
	}
	if(store_queue)
	{
		while(store_queue)
		{
			pLink = store_queue;
			store_queue = store_queue->Next;
			P_SAFE_DELETE(pLink);
		}
		store_queue= NULL;
	}
	start_x = lStartX =  StartX/32;
	start_y = lStartY = StartY/32;
	end_x = lEndX = EndX/32;
	end_y = lEndY = EndY/32;
	memset(pathX, -1, TABLE_X*TABLE_Y*sizeof(int));
	memset(pathY, -1, TABLE_X*TABLE_Y*sizeof(int));
	level = 0;
	if((start_x == end_x)&&(start_y == end_y))
	{
		return;
	}
	int nx, ny ,i;
	path1_X = pathX;
	path1_Y = pathY;
	do
	{
		nx = abs(end_x - lStartX);
		ny = abs(end_y - lStartY);
		if(nx > 32)
			if(end_x > start_x)
				lEndX = lStartX + 32;
			else
				lEndX = lStartX - 32;
		if(ny > 32)
			if(end_y > start_y)
				lEndY = lStartY + 32;
			else
				lEndY = lStartY - 32;
		FindWay( );
		if(IsFound == false)
		{
			IsFound = false;

			long lNearX, lNearY, lR;
			bool IsFindNear = false;
			lR = 0;
			while(!IsFindNear)
			{
				lR ++;			
				for(i = 0; i < 360; i +=1)
				{
					lNearX = (long)(lR*cos_O[i]) + lEndX;
					lNearY = (long)(lR*sin_O[i]) + lEndY;
					if(lNearX < 0)
						lNearX = 0;
					if(lNearY < 0)
						lNearY = 0;
					if(lNearX > Map->pHeader.nWidth-1)
						lNearX = Map->pHeader.nWidth-1;
					if(lNearY > Map->pHeader.nHeight-1)
						lNearY = Map->pHeader.nHeight-1;
					if(dis_map[lNearY-iPageStartY][lNearX-iPageStartX] != 0xffffffff)
					{
						IsFindNear = true;
						break;
					}
				}
			}
			lEndX = lNearX;
			lEndY = lNearY;
			FindWay( );
		}
		lStartX = lEndX;
		lStartY = lEndY;
	}while((nx > 32)||(ny > 32));
		
	end_x = lEndX;
	end_y = lEndY;
	pLink = NULL;
	if(dis_map)
	{
		PA_SAFE_DELETE(dis_map);
	}
}

void FINDPATH_A8::init_queue()
{
	sort_queue = new LINK;
	sort_queue->node = NULL;
	sort_queue->f = -1;
	sort_queue->Next = new LINK;
	sort_queue->Next->node = NULL;
	sort_queue->Next->f = MAXINT;
	sort_queue->Next->Next = NULL;

	store_queue = new LINK;
	store_queue->node = NULL;
	store_queue->f = -1;
	store_queue->Next = NULL;
}

void FINDPATH_A8::enter_queue(TREE * node,int f)
{
	LINK * p = sort_queue;
	LINK * father, * q;
	while((f > p->f) &&(p != NULL))
	{
		father=p;
		p=p->Next;
	}
	q= new LINK;
	q->f = f;
	q->node = node;
	q->Next = p;
	father->Next = q;
}

TREE * FINDPATH_A8::get_from_queue()
{
	LINK * bestchoice = sort_queue->Next;
	LINK * next = sort_queue->Next->Next;
	sort_queue->Next = next;
	
	bestchoice->Next = store_queue->Next;
	store_queue->Next = bestchoice;
	return bestchoice->node;
}

int FINDPATH_A8::trytile(int x,int y,TREE * father)
{
	TREE * p=father;
	unsigned int h;
	if(Map->pSurfaceData[y*Map->pHeader.nWidth+x].nPass == 0)
		return 1;											// 如果 (x,y) 处是障碍,失败
	if((x >= iPageStartX + TABLE_X)||(y >= iPageStartY + TABLE_Y)||(x < iPageStartX)||(y < iPageStartY))
		return 1;											//如果越界，失败
	if((x >= Map->pHeader.nWidth)||(x < 0)||(y >= Map->pHeader.nWidth)||(y < 0))
		return 1;
	h = father->h+1;
	if (h >= dis_map[y-iPageStartY][x-iPageStartX]) 
		return 1;											// 如果曾经有更好的方案移动到 (x,y) 失败
	dis_map[y-iPageStartY][x-iPageStartX] = h;				// 记录这次到 (x,y) 的距离为历史最佳距离
	
// 将这步方案记入待处理队列

	p = new TREE;
	p->father = father;
	p->h = father->h+1;
	p->x = x;
	p->y = y;
	enter_queue(p,p->h + judge(x, y));
	return 0;
}

void FINDPATH_A8::pop_stack()
{
	LINK * s = store_queue->Next;
	if(s != NULL)
	{
		store_queue->Next = store_queue->Next->Next;
		P_SAFE_DELETE(s->node);
		P_SAFE_DELETE(s);
	}
}

void FINDPATH_A8::freetree()
{
	LINK * p;
	if(store_queue)
		while(store_queue)
		{
			p=store_queue;
			P_SAFE_DELETE(p->node);
			store_queue=store_queue->Next;
			P_SAFE_DELETE(p);
		}
	if(sort_queue)
		while (sort_queue) 
		{
			p=sort_queue;
			P_SAFE_DELETE(p->node);
			sort_queue=sort_queue->Next;
			P_SAFE_DELETE(p);
		}
}

int FINDPATH_A8::judge(int x, int y)
{
	int distance;
	distance=abs(lEndX-x)+abs(lEndY-y);
	return distance;
}


void FINDPATH_A8::FindWay( )
{
	TREE * root;
	int i;
	if(dis_map)
		PA_SAFE_DELETE(dis_map);
	dis_map = (unsigned int **)new unsigned int[TABLE_Y];
	for(i = 0; i < TABLE_Y; i++)
	{
		dis_map[i] = new unsigned int[TABLE_X];
		memset(dis_map[i],0xff,TABLE_X*sizeof(unsigned int)); //填充dis_map为0XFF，表示各点未曾经过
	}
	init_queue();
	iPageStartX = (lStartX+lEndX-TABLE_X)>>1;
	iPageStartY = (lStartY+lEndY-TABLE_Y)>>1;

	root = new TREE;
	root->x = lStartX;
	root->y = lStartY;
	root->h = 0;
	root->father = NULL;
	enter_queue(root,judge(lStartX,lStartY));
	for (;;) 
	{
		int child, x, y;
		root=get_from_queue();
		if (root==NULL) 
		{
			return;
		}
		x = root->x;
		y = root->y;
		if (x == lEndX && y == lEndY)
			break;							// 达到目的地成功返回
		child=trytile(x,y-1,root);			//尝试向上移动
		child&=trytile(x,y+1,root);			//尝试向下移动
		child&=trytile(x-1,y,root);			//尝试向左移动
		child&=trytile(x+1,y,root);			//尝试向右移动
		child&=trytile(x+1,y-1,root);		//尝试向右上移动
		child&=trytile(x+1,y+1,root);		//尝试向右下移动
		child&=trytile(x-1,y+1,root);		//尝试向左下移动
		child&=trytile(x-1,y-1,root);		//尝试向左上移动
		
		if (child!=0)
			pop_stack();					// 如果四个方向均不能移动,释放这个死节点
	}
	// 回溯树，将求出的最佳路径保存在 path[] 中
	for (i=0; root; i++) 
	{
		path1_X[i] = (root->x)<<5;
		path1_Y[i] = (root->y)<<5;
		root=root->father;
		level++;
	}
	level -= 2;
	path1_X += i;
	path1_Y += i;
	freetree();
	root = NULL;
	IsFound = true;
}





//************************************************************************************//

FINDPATH_A4::FINDPATH_A4( )
{
	sort_queue	= NULL;
	store_queue	= NULL;
	pLink		= NULL;
	dis_map		= NULL;
	path1_X		= NULL;
	path1_Y		= NULL;
	bBeginDir	= false;
	IsFound		= false;
	memset(pathX, -1, TABLE_X*TABLE_Y*sizeof(int));
	memset(pathY, -1, TABLE_X*TABLE_Y*sizeof(int));
}

void FINDPATH_A4::find(long StartX, long StartY, long EndX, long EndY)
{
	IsFound	= false;
	level = 0;
	if(sort_queue)
	{
		while(sort_queue)
		{
			pLink = sort_queue;
			sort_queue = sort_queue->Next;
			P_SAFE_DELETE(pLink);
		}
		sort_queue= NULL;
	}
	if(store_queue)
	{
		while(store_queue)
		{
			pLink = store_queue;
			store_queue = store_queue->Next;
			P_SAFE_DELETE(pLink);
		}
		store_queue= NULL;
	}
	start_x = lStartX =  StartX/32;
	start_y = lStartY = StartY/32;
	end_x = lEndX = EndX/32;
	end_y = lEndY = EndY/32;
	memset(pathX, -1, TABLE_X*TABLE_Y*sizeof(int));
	memset(pathY, -1, TABLE_X*TABLE_Y*sizeof(int));
	if((start_x == end_x)&&(start_y == end_y))
	{
		return;
	}
	int nx, ny ,i;
	path1_X = pathX;
	path1_Y = pathY;
	do
	{
		nx = abs(end_x - lStartX);
		ny = abs(end_y - lStartY);
		if(nx > 32)
			if(end_x > start_x)
				lEndX = lStartX + 32;
			else
				lEndX = lStartX - 32;
		if(ny > 32)
			if(end_y > start_y)
				lEndY = lStartY + 32;
			else
				lEndY = lStartY - 32;
		FindWay( );
		if(IsFound == false)
		{
			IsFound = false;

			long lNearX, lNearY, lR;
			bool IsFindNear = false;
			lR = 0;
			while(!IsFindNear)
			{
				lR ++;			
				for(i = 0; i < 360; i +=1)
				{
					lNearX = (long)(lR*cos_O[i]) + lEndX;
					lNearY = (long)(lR*sin_O[i]) + lEndY;
					if(lNearX < 0)
						lNearX = 0;
					if(lNearY < 0)
						lNearY = 0;
					if(lNearX > Map->pHeader.nWidth-1)
						lNearX = Map->pHeader.nWidth-1;
					if(lNearY > Map->pHeader.nHeight-1)
						lNearY = Map->pHeader.nHeight-1;
					if(dis_map[lNearY-iPageStartY][lNearX-iPageStartX] != 0xffffffff)
					{
						IsFindNear = true;
						break;
					}
				}
			}
			lEndX = lNearX;
			lEndY = lNearY;
			FindWay( );
		}
		lStartX = lEndX;
		lStartY = lEndY;
	}while((nx > 32)||(ny > 32));
		
	end_x = lEndX;
	end_y = lEndY;
	pLink = NULL;
	if(dis_map)
	{
		PA_SAFE_DELETE(dis_map);
	}
}

void FINDPATH_A4::init_queue()
{
	sort_queue = new LINK;
	sort_queue->node = NULL;
	sort_queue->f = -1;
	sort_queue->Next = new LINK;
	sort_queue->Next->node = NULL;
	sort_queue->Next->f = MAXINT;
	sort_queue->Next->Next = NULL;

	store_queue = new LINK;
	store_queue->node = NULL;
	store_queue->f = -1;
	store_queue->Next = NULL;
}

void FINDPATH_A4::enter_queue(TREE * node,int f)
{
	LINK * p = sort_queue;
	LINK * father, * q;
	while((f > p->f) &&(p != NULL))
	{
		father=p;
		p=p->Next;
	}
	q= new LINK;
	q->f = f;
	q->node = node;
	q->Next = p;
	father->Next = q;
}

TREE * FINDPATH_A4::get_from_queue()
{
	LINK * bestchoice = sort_queue->Next;
	LINK * next = sort_queue->Next->Next;
	sort_queue->Next = next;
	
	bestchoice->Next = store_queue->Next;
	store_queue->Next = bestchoice;
	return bestchoice->node;
}

int FINDPATH_A4::trytile(int x,int y,TREE * father)
{
	TREE * p=father;
	unsigned int h;
	if(Map->pSurfaceData[y*Map->pHeader.nWidth+x].nPass == 0)
		return 1;											// 如果 (x,y) 处是障碍,失败
	if((x >= iPageStartX + TABLE_X)||(y >= iPageStartY + TABLE_Y)||(x < iPageStartX)||(y < iPageStartY))
		return 1;											//如果越界，失败
	if((x >= Map->pHeader.nWidth)||(x < 0)||(y >= Map->pHeader.nWidth)||(y < 0))
		return 1;
	h = father->h+1;
	if (h >= dis_map[y-iPageStartY][x-iPageStartX]) 
		return 1;											// 如果曾经有更好的方案移动到 (x,y) 失败
	dis_map[y-iPageStartY][x-iPageStartX] = h;				// 记录这次到 (x,y) 的距离为历史最佳距离
	
// 将这步方案记入待处理队列

	p = new TREE;
	p->father = father;
	p->h = father->h+1;
	p->x = x;
	p->y = y;
	enter_queue(p,p->h + judge(x, y));
	return 0;
}

void FINDPATH_A4::pop_stack()
{
	LINK * s = store_queue->Next;
	if(s != NULL)
	{
		store_queue->Next = store_queue->Next->Next;
		P_SAFE_DELETE(s->node);
		P_SAFE_DELETE(s);
	}
}

void FINDPATH_A4::freetree()
{
	LINK * p;
	if(store_queue)
		while(store_queue)
		{
			p=store_queue;
			P_SAFE_DELETE(p->node);
			store_queue=store_queue->Next;
			P_SAFE_DELETE(p);
		}
	if(sort_queue)
		while (sort_queue) 
		{
			p=sort_queue;
			P_SAFE_DELETE(p->node);
			sort_queue=sort_queue->Next;
			P_SAFE_DELETE(p);
		}
}

int FINDPATH_A4::judge(int x, int y)
{
	int distance;
	distance=abs(lEndX-x)+abs(lEndY-y);
	return distance;
}


void FINDPATH_A4::FindWay( )
{
	TREE * root;
	int i;
	if(dis_map)
		PA_SAFE_DELETE(dis_map);
	dis_map = (unsigned int **)new unsigned int[TABLE_Y];
	for(i = 0; i < TABLE_Y; i++)
	{
		dis_map[i] = new unsigned int[TABLE_X];
		memset(dis_map[i],0xff,TABLE_X*sizeof(unsigned int)); //填充dis_map为0XFF，表示各点未曾经过
	}
	init_queue();
	iPageStartX = (lStartX+lEndX-TABLE_X)>>1;
	iPageStartY = (lStartY+lEndY-TABLE_Y)>>1;

	root = new TREE;
	root->x = lStartX;
	root->y = lStartY;
	root->h = 0;
	root->father = NULL;
	enter_queue(root,judge(lStartX,lStartY));
	for (;;) 
	{
		int child, x, y;
		root=get_from_queue();
		if (root==NULL) 
		{
			return;
		}
		x = root->x;
		y = root->y;
		if (x == lEndX && y == lEndY)
			break;							// 达到目的地成功返回
		child=trytile(x,y-1,root);			//尝试向上移动
		child&=trytile(x,y+1,root);			//尝试向下移动
		child&=trytile(x-1,y,root);			//尝试向左移动
		child&=trytile(x+1,y,root);			//尝试向右移动
//		child&=trytile(x+1,y-1,root);		//尝试向右上移动
//		child&=trytile(x+1,y+1,root);		//尝试向右下移动
//		child&=trytile(x-1,y+1,root);		//尝试向左下移动
//		child&=trytile(x-1,y-1,root);		//尝试向左上移动
		
		if (child!=0)
			pop_stack();					// 如果四个方向均不能移动,释放这个死节点
	}
	// 回溯树，将求出的最佳路径保存在 path[] 中
	for (i=0; root; i++) 
	{
		path1_X[i] = (root->x)<<5;
		path1_Y[i] = (root->y)<<5;
		root=root->father;
		level++;
	}
	level -= 2;
	path1_X += i;
	path1_Y += i;
	freetree();
	root = NULL;
	IsFound = true;
}